﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _4Gewinnt
{

    public class MiniMax
    {

        // The colors of MIN and MAX
        private GameColor MAX;
        private GameColor MIN;

        // This board stores the various game situtations which appear while traversing the miniMax tree.
        public RedoBoard miniMaxBoard;

        //Die Ausgangssituation
        public Node root;

        // Diese Variable wird benutzt, um den "kleinen" und "großen" Minimax auseinander zu halten.
        public int initialDepth = 0;
        private int[] MAX_ROW;
        private int[] MIN_ROW;

        /// <summary>
        /// sbr: Konstruktor des MiniMax-Algorithmus mit (teilweisem) alpha-beta-Pruning.
        /// Unser MinMax läuft in mehreren Phasen wie folgt:
        /// 1. Phase: Vorausschau von 2 Zügen (1 Zug MAX, dann 1 Zug MIN). Sollte durch den Zug von MAX sich die Möglichkeit ergeben, dass MIN eine 4er-Reihe legen kann, wird in die Spalte, die dies ermöglicht, natürlich
        /// nicht gezogen. Diese Spalte wird auch für die folgenden Phasen des MinMax-Algos nicht berücksichtigt.
        /// 2. Phase (diese Phase läuft erst nach mindestens 11 gespielten Steinen): Vorausschau von 6 Zügen: Suche nach solchen Situationen, in denen der Gegner zwei Bedrohungen innerhalb einer Spalte direkt übereinander erreichen kann. Sollte
        /// eine solche Situation gefunden werden, versuche diese zu verhindern. Recht zuverlässig verhindert werden solche Situationen, wo die beiden die Bedrohung erzeugenden 3er-Reihen einen gemeinsamen Stein haben.
        /// Dann setzen wir in die Spalte des gemeinsamen Steins (wir haben ja vorausgeschaut und möglicherweise ist der entsprechende Stein noch nicht gelegt). Sollten die beiden die Bedrohung erzeugenden 3er-Reihen
        /// keinen gemeinsamen Stein haben, setze in eine der beiden Spalten, die sich neben der Spalte mit den beiden Bedrohungen befinden und hoffe das Beste ;-) In dieser Phase wird der "reine" MinMax-Algorithmus
        /// ohne alpha-beta-Pruning benutzt.
        /// 3. Phase (diese Phase läuft nur, wenn die 2te Phase keine doppelten Bedrohungen verhindern muss): Vorausschau von 5 Zügen: Die Spielsituation wird mit Hilfe der Anzahl von xer-Reihen bewertet. Die Anzahl der
        /// xer-Reihen wird gewichtet, wobei 3er-Reihen natürlich höher gewichtet werden als 2er-Reihen. Mathematisch: Summe von i = 0 bis 7 (w_i * #ier-Reihen von MAX) - Summe von i = 0 bis 7 (w_i * #ier-Reihen von MIN)
        /// mit w_i Gewichte (Gewichte sind in Node.MAX_ROW und Node.MIN_ROW). Alpha-Beta-Pruning wird angewendet.
        /// </summary>
        /// <param name="max">Wir</param>
        /// <param name="min">Der Gegner</param>
        public MiniMax(GameColor max, GameColor min)
        {
            this.MAX = max;
            this.MIN = min;
        }

        public MiniMax(GameColor max, GameColor min, int[] MAX_ROW, int[] MIN_ROW) : this(max, min)
        {
            this.MAX_ROW = MAX_ROW;
            this.MIN_ROW = MIN_ROW;
        }

        /// <summary>
        /// Starts the MiniMax algorithm
        /// </summary>
        /// <param name="board">The current game state from which to start the search</param>
        /// <param name="depth">The desired depth</param>
        /// <param name="anzahlGespielteZuege">Die Anzahl der gespielten Züge</param>
        /// <returns>The column where to put the next coin</returns>
        public int minimax(RedoBoard board, int depth, int anzahlGespielteZuege)
        {
            miniMaxBoard = board.Clone();
            initialDepth = depth;

            root = new Node(-1, MAX, MIN, true, MAX_ROW, MIN_ROW);

            // Alpha-Beta pruning variables, initialized with highes/smalles values
            int alpha = int.MinValue;
            int beta = int.MaxValue;
            // The highest score
            int score = int.MinValue;
            // The column where we put our next coin.
            int column = -1;

            List<Node> children = root.getChildren(miniMaxBoard);

            foreach (Node child in children)
            {
                //Max beginnt mit dem Ziehen
                int tmp = this.max(child, depth, alpha, beta);
                // Sollten wir in eine Spalte nicht mehr legen dürfen, wird dieser Knoten und seine Kindknoten bei dem "großen" Minimax nicht mehr berücksichtigt.
                if (tmp == int.MinValue)
                {
                    child.consider = false;
                }
                else if (score <= tmp && miniMaxBoard.isLegalColumn(child.column))
                {
                    score = tmp;
                    // Remember which draw to make
                    column = child.column;
                }
            }

            //sbr: Falls mehr als 10 Züge gemacht wurden, starte mit der Phase, in der doppelte Bedrohungen verhindert werden
            if (anzahlGespielteZuege > 10)
            {
                //liefert die Zeile zurück, die doppelte Bedrohungen verhindern könnte. Ansonsten -1.
                column = minimaxThreatKiller(board, 4, children);
                if (column != -1)
                {
                    if (!board.isLegalColumn(column))
                    {
                        column = -1;
                    }
                }
            }

            //sbr: In den ersten 10 Zügen wird diese 3. Phase immer gestartet. Danach nur noch, wenn die 2. Phase keine Spalte gefunden hat.
            if ((column == -1 && anzahlGespielteZuege > 10) || (column != -1 && anzahlGespielteZuege <= 10))
            {
                //sbr: Start der 2.Stufe des Minmax-Algos. Dieser wird nur für die Columns ausgeführt, in
                //die wir reinlegen dürfen.
                column = minimaxThirdStage(board, 4, children);
            }

            return column;
        }

        /// <summary>
        /// sbr: Diese Phase des MinMax-Algorithmus versucht doppelte Bedrohungen des Gegners zu verhindern. Es wird kein alpha-beta-Pruning vorgenommen, da diese Situationen nicht bewertet werden, sondern nur nach einer
        /// Spalte gesucht wird. Aus der Rekursion zurückgeliefert wird eine genaue Position, wo der Stein hinsoll. Möglicherweise können wir dort aber noch gar nicht hinlegen, weil es keine darunter liegenden Steine gibt.
        /// In diesem Fall warte ab.
        /// </summary>
        /// <param name="board">Die Spielsituation</param>
        /// <param name="depth">Die Tiefe, in der gesucht werden soll</param>
        /// <param name="children">Die bereits durch die 1. Phase generierten Kinder</param>
        /// <returns>Die Spalte, die doppelte Bedrohungen verhindert. Gibt es keine solche, -1.</returns>
        private int minimaxThreatKiller(RedoBoard board, int depth, List<Node> children)
        {
            miniMaxBoard = board.Clone();
            initialDepth = depth;

            foreach (Node child in children)
            {
                //Nur für die Knoten ausführen, in die wir legen dürfen (Ausschluss durch 1.Phase)
                if (child.consider == true)
                {
                    Tuple<int, int> tmp = this.max(child, depth);

                    //Finden wir eine Spalte, die doppelte Bedrohungen verhindert, geben wir sie direkt zurück.
                    if (tmp.Item1 != -1 && tmp.Item2 != -1)
                    {
                        if (!board.isFieldFree(tmp.Item2 + 1, tmp.Item1) && board.isFieldFree(tmp.Item2, tmp.Item1))
                        {
                            return tmp.Item1;
                        }
                        else
                        {
                            return -1;
                        }
                    }
                }
            }
            return -1;
        }


        /// <summary>
        /// sbr: Die dritte Phase des MinMax-Algorithmus. Alpha-Beta-Pruning wird verwendet. Bei gleicher Bewertung von verschiedenen Spalten wird immer die mittigste genommen.
        /// </summary>
        /// <param name="board">The current game state from which to start the search</param>
        /// <param name="depth">The desired depth</param>
        /// <param name="children">Die bereits berechneten Knoten aus Phase 1 des Minimax</param>
        /// <returns>The column where to put the next coin</returns>
        private int minimaxThirdStage(RedoBoard board, int depth, List<Node> children)
        {
            miniMaxBoard = board.Clone();
            initialDepth = depth;

            //Alpha-Beta pruning variables, initialized with highes/smalles values
            int alpha = int.MinValue;
            int beta = int.MaxValue;
            // The highest score
            int score = int.MinValue;
            // The column where we put our next coin.
            int column = -1;
            int count = 0;

            //sbr: Falls mehrere Spalten die gleiche Bewertung erhalten haben
            Dictionary<int, int> scores = new Dictionary<int, int>();

            foreach (Node child in children)
            {
                //sbr: Betrachte nur Knoten, die nicht durch Phase 1 rausgeschmissen wurden
                if (child.consider == true)
                {
                    count++;
                    int tmp = this.max(child, depth, alpha, beta);
                    // Check if we found a draw, which has a higher rating
                    Console.WriteLine("Spalte " + child.column + " mit Score " + tmp);
                    if (score <= tmp && miniMaxBoard.isLegalColumn(child.column))
                    {
                        score = tmp;
                        // Remember which draw to make
                        column = child.column;
                        scores.Add(column, score);
                    }
                }
            }

            //sbr: Sollten mehrere Spalten dieselbe Bewertung erhalten, wähle die aus, die der Mitte am nächsten ist.
            if (scores.Count != 0)
            {
                int highestScore = scores.Values.Max();
                List<int> keyList = new List<int>();

                //sbr: Füge alle Spalten mit nicht höchster Bewertung in keyList ein
                foreach (KeyValuePair<int, int> pair in scores)
                {
                    if (pair.Value != highestScore)
                    {
                        keyList.Add(pair.Key);
                    }
                }

                //sbr: Schmeisse dann die Spalten raus, die nicht die höchste Bewertung haben.
                for (int i = 0; i < keyList.Count; i++)
                {
                    scores.Remove(keyList.ElementAt(i));
                }

                //sbr: Mindestens 2 Spalten mit gleicher höchster Bewertung
                if (scores.Count > 1)
                {
                    //Hmm...irgendwie grade Brett vorm Kopf. Kann man das besser lösen, dass man den Wert nimmt, der 3 am nächsten ist???
                    List<int> columns = new List<int>();
                    Random zufall = new Random();
                    Double zufallszahl = zufall.NextDouble();
                    foreach (KeyValuePair<int, int> kp in scores)
                    {
                        columns.Add(kp.Key);
                    }

                    if (columns.Contains(3))
                    {
                        column = 3;
                    }
                    else if (columns.Contains(4) && columns.Contains(2))
                    {
                        if (zufallszahl <= 0.5)
                        {
                            column = 4;
                        }
                        else
                        {
                            column = 2;
                        }
                    }
                    else if (columns.Contains(4))
                    {
                        column = 4;
                    }
                    else if (columns.Contains(2))
                    {
                        column = 2;
                    }
                    else if (columns.Contains(1) && columns.Contains(5))
                    {
                        if (zufallszahl <= 0.5)
                        {
                            column = 1;
                        }
                        else
                        {
                            column = 5;
                        }
                    }
                    else if (columns.Contains(1))
                    {
                        column = 1;
                    }
                    else if (columns.Contains(5))
                    {
                        column = 5;
                    }
                    else if (columns.Contains(0) && columns.Contains(6))
                    {
                        if (zufallszahl <= 0.5)
                        {
                            column = 6;
                        }
                        else
                        {
                            column = 0;
                        }
                    }
                    else if (columns.Contains(0))
                    {
                        column = 0;
                    }
                    else if (columns.Contains(6))
                    {
                        column = 6;
                    }
                }
            }

            //sbr: Möglicherweise müssen wir in eine Spalte schmeissen, wodurch wir verlieren, weil es keine anderen mehr gibt (die 1. Stage des MinMax-Algos hat alle Spalten rausgeschmissen). 
            //Schmeisse daher in irgendeine.
            if (count == 0)
            {
                for (int i = 0; i < miniMaxBoard.Cols; i++)
                {
                    if (miniMaxBoard.isLegalColumn(i))
                    {
                        column = i;
                    }
                }
            }

            return column;
        }


        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MAXs turn.
        /// </summary>
        /// <param name="node">The current node (Max node)</param>
        /// <param name="depth">The current depth, if it equals 0 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The maximum reachable score from node</returns>
        public int max(Node node, int depth, int alpha, int beta)
        {
            try
            {
                int localAlpha = int.MinValue;
                // Update game state
                miniMaxBoard.moveTo(MAX, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    int mScore = node.getScore(miniMaxBoard, initialDepth, false);
                    return mScore;
                }

                // Stores the score of the children
                int score = 0;

                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    score = this.min(child, depth - 1, alpha, beta);
                    // Check if we can prun the subtree. We can prun it, if MIN would never 
                    // choose the current state, because he found a better one.

                    //sbr: Dieser Teil ist nicht Bestandteil des "normalen" Minmax. Dieser wird auch
                    //nur dafür benötigt, dass Spalten rausgeschmissen werden, in die wir nicht
                    //reinlegen dürfen, weil sonst der Gegner gewinnt (aus Phase 1).
                    if (score == int.MinValue && initialDepth == 1)
                    {
                        localAlpha = score;
                        return localAlpha;
                    }
                    if (score > localAlpha)
                    {
                        if (score >= beta)
                        {
                            return score;
                        }
                        localAlpha = score;
                        if (score > alpha)
                        {
                            alpha = score;
                        }
                    }
                }
                return localAlpha;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);

            }
        }

        /// <summary>
        /// Invoked by the second phase of the MiniMax Algorithm if its MAXs turn.
        /// </summary>
        /// <param name="node">The current node (Max node)</param>
        /// <param name="depth">The current depth, if it equals 0 a leafe is reached</param>
        /// <returns>The maximum reachable score from node</returns>
        public Tuple<int, int> max(Node node, int depth)
        {
            try
            {
                // Update game state
                miniMaxBoard.moveTo(MAX, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    Tuple<int, int> mPreventionTuple = node.getTupleToPreventDoubleThreats(miniMaxBoard);
                    return mPreventionTuple;
                }

                // Stores the score of the children
                Tuple<int, int> preventionTuple = new Tuple<int, int>(-1, -1);

                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    preventionTuple = this.min(child, depth - 1);
                    if (preventionTuple.Item1 != -1 && preventionTuple.Item2 != -1)
                    {
                        child.consider = false;
                        break;
                    }
                }
                return preventionTuple;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);
            }
        }


        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MINs turn.
        /// </summary>
        /// <param name="node">The current node (MIN node)</param>
        /// <param name="depth">The current depth, if it equals 0 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The minimum reachable score from node</returns>
        public int min(Node node, int depth, int alpha, int beta)
        {
            try
            {
                int localBeta = int.MaxValue;
                // Update game state
                miniMaxBoard.moveTo(MIN, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    int mScore = node.getScore(miniMaxBoard, initialDepth, false);
                    return mScore;
                }
                // Stores the score of the children
                int score = 0;

                // Its MINs turn
                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MIN is minimizing (bad states for MAX are good ones for MIN)
                    score = this.max(child, depth - 1, alpha, beta);
                    // Like above we check whether we can prun the subtree
                    if (score < localBeta)
                    {
                        if (score <= alpha)
                        {
                            return score;
                        }
                        localBeta = score;
                        if (score < beta)
                        {
                            beta = score;
                        }
                    }
                }

                return localBeta;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);
            }
        }

        /// <summary>
        /// Invoked by the second phase of the MiniMax Algorithm if its MINs turn.
        /// </summary>
        /// <param name="node">The current node (MIN node)</param>
        /// <param name="depth">The current depth, if it equals 0 a leafe is reached</param>
        /// <returns>The minimum reachable score from node</returns>
        public Tuple<int, int> min(Node node, int depth)
        {
            try
            {
                // Update game state
                miniMaxBoard.moveTo(MIN, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    Tuple<int, int> mPreventionTuple = node.getTupleToPreventDoubleThreats(miniMaxBoard);
                    return mPreventionTuple;
                }
                // Stores the score of the children
                Tuple<int, int> preventionTuple = new Tuple<int, int>(-1, -1);

                // Its MINs turn
                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MIN is minimizing (bad states for MAX are good ones for MIN)
                    preventionTuple = this.max(child, depth - 1);
                    if (preventionTuple.Item1 != -1 && preventionTuple.Item2 != -1)
                    {
                        break;
                    }
                }

                return preventionTuple;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);
            }
        }

    }
}

